The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
An encryption method is length-preserving if the ciphertext has exactly the same number of bits as the plaintext. Such a method must be deterministic, since it is impossible to accommodate random data (such as an initialization vector) within the ciphertext. Further, deterministic length-preserving encryption is well suited to certain applications. For example, in some encrypted database applications, determinism is essential to ensure that plaintext values in a lookup operation exactly correspond to previously stored ciphertext values.
Further, in some applications of cryptology, it is not possible to provide certain desirable security services, such as message authentication on data, because it is not possible to expand the data to include a message authentication code. For example, the Secure Real Time Protocol (SRTP) in some networks (for example, some wireless network scenarios) cannot expand the plaintext data. Length-preserving algorithms essentially implement a codebook; repeated encryptions of the same plaintext with the same key result in identical ciphertext. An adversary gains knowledge about the plaintext by seeing which ciphertext values match. Nevertheless, in some scenarios length-preserving encryption is still useful. For example, length preservation may enable encryption to be introduced into data processing systems that are already implemented and deployed, or used in protocols that have fixed-width fields, or in systems that limit the allowed amount of data expansion. In these situations, as an alternative to message authentication, a length-preserving, deterministic, nonmalleable encryption method is desirable.
Informally, a cipher is nonmalleable if changing a single bit of a ciphertext value affects all of the bits of the corresponding plaintext. Thus, in nonmalleable encryption it is impossible to manipulate the appearance of plaintext after decryption by manipulating the ciphertext. More formally, a desirable nonmalleable cipher implements a pseudorandom permutation; it is indistinguishable from a permutation on the set of messages to a computationally bounded adversary. It is desirable for such a cipher to handle plaintexts of variable size, and therefore there is a need for a cipher that provides a pseudorandom arbitrary length permutation: for each of the possible plaintext lengths, the cipher acts as a pseudorandom permutation.
Nonmalleable encryption is a significant improvement over conventional modes of operation, such as cipher block chaining and counter-mode encryption, whenever adding a message authentication tag is impossible. In addition, a nonmalleable cipher can also accept an additional input value that can be used to prevent ciphertext-substitution attacks. For example, an SRTP sequence number can be used in implementations that are associated with network elements running SRTP.
Nonmalleable encryption also is useful for disk-block encryption. Such encryption is often used in remote storage systems, since it allows storage area networks to be used in applications in which the administrator of the network is trusted only to a limited extent.
There have been many nonmalleable cipher proposals in the theoretical literature. An embodiment of the approach disclosed herein, which may be referred to as an extended codebook (XCB) mode of operation for block ciphers, differs from prior work in several ways. A cipher proposed by Luby and Rackoff in the 1980s (“LR” herein) provides a theoretical basis for much past work in nonmalleable ciphers. XCB is different from this work in that uses a different set of computations; XCB is not a Fesitel cipher, while LR is. XCB relies on the invertibility of the block cipher, while LR does not. Also, LR needs four rounds to be secure, while XCB is secure with three.
In the 1990s, Naor & Reingold published some optimizations on the basic idea, as described in “On the Construction of Pseudo-Random Permutations: Luby Rackoff Revisited”. This work uses four rounds, but has the first and fourth be “pairwise independent” permutations, as defined by Naor & Reingold. The Naor-Reingold approach also does not rely on the invertibility of the block cipher. This design is completely different than XCB, which just uses three rounds, does not use pairwise independent permutations, and does rely on the invertibility of the block cipher.
In the 1990s, Stefan Lucks described the use of hash functions in “Faster Luby-Rackoff Ciphers”. Anderson and Biham also published some similar work, showing two ciphers BEAR and LION. This work discusses only LR constructions, and does not rely on the invertibility of the block cipher. Furthermore, it requires four rounds in order to be secure.
More recently, Patel, Ramzan, Sundaram published two papers that extend the Naor-Reingold work, “Towards Making Luby-Rackoff Ciphers Optimal and Practical” and “Luby-Rackoff Ciphers over Finite Algebraic Structures or Why XOR is not so Exclusive”. This work builds on that of Naor-Reingold, and all of the comments for that work apply to these designs.
Bellare and Rogaway described a mode of operation that is length-preserving, but is not nonmalleable, in “On the Construction of Variable-Input-Length Ciphers”. They call this work VIL, and it differs significantly from XCB.
Rogaway and Halevi designed the EME mode of operation, which is nonmalleable, in “The EMD Mode of Operation (A Tweaked, Wide-Blocksize, Strong PRP)” and “EME ?: extending EME to handle arbitrary-length messages with associated data”. This work has goals that are identical to that of XCB, but the design of EME is different from that of XCB. Importantly, EME requires twice as many invocations of the block cipher as XCB.
Independently, McGrew and Viega submitted an optimized Luby-Rackoff design called ABL (Arbitrary Block Length Mode) to the IEEE Security in Storage Working Group. XCB is significantly different from ABL.
Patel et al. have published a paper entitled “Efficient Constructions of Variable-Input-Length Block Ciphers” that describes two cipher constructions. The approach of Section 3 is structured such that the hash invocation (round 1) and the block cipher invocation (round 2) cannot be done in parallel. In contrast, in XCB the first two rounds can be done in parallel. The ability for XCB to do these operations simultaneously is a significant performance benefit to a high-speed hardware implementation. Further, the Section 3 cipher has only a single hash function application and a single block cipher invocation, outside of the “counter mode” used in round 3. Because of this, it is not secure against chosen plaintext/ciphertext attacks. Thus, the Section 3 approach provides only a pseudorandom permutation, not a “super pseudorandom permutation.” In contrast, XCB has two hash invocations and two block cipher invocations, and is a super pseudorandom permutation.